#include <iostream>
#include <map>
#include <vector>
using namespace std;
class Solution {
public:
  vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2) {
    map<int, int> countmap;
    vector<int> res;
    for (auto p = arr1.begin(); p != arr1.end(); ++p) {
      if (countmap.find(*p) != countmap.end()) {
        countmap[*p]++;
      } else {
        countmap[*p] = 1;
      }
    }
    for (auto p = arr2.begin(); p != arr2.end(); ++p) {
      for (int count = countmap[*p]; count > 0; --count) {
        res.push_back(*p);
      }
      countmap.erase(*p);
    }
    for (auto p = countmap.begin(); p != countmap.end(); ++p) {
      for (int count = p->second; count > 0; --count) {
        res.push_back(p->first);
      }
      countmap.erase(p);
    }
    return res;
  }
};

int main()
{
	vector<int> a = {2,3,1,3,2,4,6,7,9,2,19};
	vector<int> b = {2,1,4,3,9,6};
	Solution s;
	vector<int > c = s.relativeSortArray(a, b);
	for(auto p = c.begin(); p != c.end(); ++p){
		cout<<*p<<" ";
	}
	cout<<endl;
}
